package 抽象数据类型;

import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 单调栈 {
    public static int[] nextGreaterElements(int[] nums) {
        int[] arr = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= stack.peek()) {
                stack.pop();
            }
            arr[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return arr;
    }

    public static int[] nextGreaterElementsDouble(int[] vals) {
        int[] arr = new int[vals.length * 2];
        int[] nums = new int[vals.length * 2];
        System.arraycopy(vals, 0, nums, 0, vals.length);
        System.arraycopy(vals, 0, nums, vals.length, vals.length);
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= stack.peek()) {
                stack.pop();
            }
            arr[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return arr;
    }

    public static int[] nextGreaterElementsCircle(int[] nums) {
        int[] arr = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length * 2 - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i % nums.length] >= stack.peek()) {
                stack.pop();
            }
            arr[i % nums.length] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i % nums.length]);
        }
        return arr;
    }

    public static void main(String[] args) {
        nextGreaterElements(new int[]{2, 1, 2, 4, 3});
        nextGreaterElementsDouble(new int[]{2, 1, 2, 4, 3});
        nextGreaterElementsCircle(new int[]{2, 1, 2, 4, 3});
    }
}
